#include <iostream>
#include <deque>
#include <vector>
using namespace std;

//1、数组实现
const int N = 1e6 + 10;
int q[N], a[N]; //数组q用来存下标
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];

	//找滑动窗口最小值
	int hh = 0, tt = -1;
	for (int i = 0; i < n; i++) {
		if (i - q[hh] == k) hh++; //队头弹出元素
		while (hh <= tt && a[q[tt]] > a[i]) tt--; //队尾弹出元素
		q[++tt] = i; //压入下标
		if (i - k + 1 >= 0)printf("%d ", a[q[hh]]);
	}
	printf("\n");
	//找滑动窗口最大值
	hh = 0, tt = -1;
	for (int i = 0; i < n; i++) {
		if (i - q[hh] == k) hh++; //队头弹出元素
		while (hh <= tt && a[q[tt]] < a[i]) tt--; //队尾弹出元素
		q[++tt] = i; //压入下标
		if (i - k + 1 >= 0)printf("%d ", a[q[hh]]);
	}
	return 0;
}


//2、双端队列
int main() {
	int n, k;
	cin >> n >> k;
	vector<int> arr(n);
	deque<int> q;
	for (int i = 0; i < n; i++)cin >> arr[i];
	for (int i = 0; i < n; i++) {
		if (i - q.front() == k) q.pop_front();
		while (!q.empty() && arr[q.back()] > arr[i])q.pop_back();
		q.push_back(i);
		if (i - k + 1 >= 0) cout << arr[q.front()] << " ";
	}
	cout << endl;

	q.clear();
	for (int i = 0; i < n; i++) {
		if (i - q.front() == k) q.pop_front();
		while (!q.empty() && arr[q.back()] < arr[i])q.pop_back();
		q.push_back(i);
		if (i - k + 1 >=0) cout << arr[q.front()] << " ";
	}
	return 0;
}
